
package com.studiofortress.sf.structure.collisions;

import com.studiofortress.sf.structure.Action;
import com.studiofortress.sf.structure.Actor;
import com.studiofortress.sf.util.collections.CachingHashMap;
import com.studiofortress.sf.util.collections.CachingHashSet;
import com.studiofortress.sf.util.collections.CallbackIterator;
import com.studiofortress.sf.util.collections.ClassInheritenceMap;
import com.studiofortress.sf.util.collections.ObjectStack;
import com.studiofortress.sf.util.collections.Resizable2DArray;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * This uses a grid to store Actors. When Actors are added they are placed in
 * grid cells. An Actor will be placed in multiple cells if it overlaps several
 * of them.
 * 
 * When collision detection occurs the Actor is compared against only the Actors
 * which are within all the cells the Actor is within.
 * 
 * Currently the collision classes passed in does NOT take into account
 * inheritence.
 * 
 * @author Joseph Lenton
 */
/* Internally this uses heavy amounts of caching to reduce the number of
 * elements used in it's data structures. In environments with 1000s of Actors,
 * this can dramatically reduce object creation, which dramatically improves
 * garbage collection pause times.
 *
 * Rectangles are represented by 4 elements in an int array where
 *      arr[0] = minX
 *      arr[1] = maxX
 *      arr[2] = minY
 *      arr[3] = maxY
 * These positions are inclusive.
 */
public class GridCollisions<A extends Actor> implements CollisionHandler<A>
{
    // all collission points are cached so they can be used by multiple actors
    private static final ObjectStack<int[]> ARRAYS = new ObjectStack<int[]>();
    
    /**
     * This will return a int[] that represents the given X and Y
     * location. This point may or may not be a new point.
     * @param x The x-location of the point.
     * @param y The y-location of the point.
     * @return A int[] that represents the given location.
     */
    private static final int[] newRectangle(final int minX, final int maxX, final int minY, final int maxY)
    {
        if ( ARRAYS.size() > 0 ) {
            final int[] arr = ARRAYS.pop();
            
            arr[0] = minX;
            arr[1] = maxX;
            arr[2] = minY;
            arr[3] = maxY;
            
            return arr;
        } else {
            return new int[] { minX, maxX, minY, maxY };
        }
    }
    
    private static final int DEFAULT_SIZE = 100;
    
    // the width and height of each cell in the grid
    private final int gridWidth;
    private final int gridHeight;

    /* This contains a list of all of the actors in each location in the grid. */
    private final ClassInheritenceMap<A, Resizable2DArray<CachingHashSet<A>>> grid;

    /* This map of actors to a rectangle describing them is needed because it
     * matches the locations we know about in the grid.
     * If an actor changes size or location then we can use this data to work
     * out which parts of the grid they are no longer in, and should be removed
     * from. */
    private final CachingHashMap<A, int[]> actorGridPoints;
    
    // Actors are cached in this set before being updated.
    // This allows them to be updated multiple times but their grid points are
    // only calculated when an intersection occurres.

    private final IntersectingActorsAction getIntersectingActorsAction =
            new IntersectingActorsAction();

    private final CachingHashSet<A> lazyUpdateActors;
    
    private final CollisionCallback collisionCallback   = new CollisionCallback();
    private final UpdateCallback updateCallback         = new UpdateCallback();
    private final GridCallback gridCallback             = new GridCallback();
    
    /**
     * Creates a new CollisionGrid with the default grid width and height of 100.
     */
    public GridCollisions()
    {
        this( DEFAULT_SIZE );
    }
    
    /**
     * A new CollisionGrid where the width and height of each cell is the same.
     * @param gridSize The width and height of each cell. Must be greater then 0.
     */
    public GridCollisions(final int gridSize)
    {
        this( gridSize, gridSize );
    }
    
    /**
     * Creates a new GridCollision where each cell in the grid is the size of
     * the given width and height.
     * @param gridWidth The width of each cell in this GridCollisions. Must be greater then 0.
     * @param gridHeight The height of each cell in this GridCollisions. Must be greater then 0.
     */
    public GridCollisions(final int gridWidth, final int gridHeight)
    {
        if ( gridWidth <= 0 ) {
            throw new IllegalArgumentException("gridWidth must be greater then 0, given: " + gridWidth);
        }
        if ( gridHeight <= 0 ) {
            throw new IllegalArgumentException("gridHeight must be greater then 0, given: " + gridHeight);
        }
        
        this.gridWidth = gridWidth;
        this.gridHeight = gridHeight;
        grid = new ClassInheritenceMap<A, Resizable2DArray<CachingHashSet<A>>>();
        actorGridPoints = new CachingHashMap<A, int[]>();

        lazyUpdateActors = new CachingHashSet<A>();
    }
    
    /**
     * @return The width of the cells used for collision detection.
     */
    public int getGridWidth()
    {
        return gridWidth;
    }
    
    /**
     * @return The height of the cells used for collision detection.
     */
    public int getGridHeight()
    {
        return gridHeight;
    }

    /**
     * Adds the given actor to this grid collissions.
     * @param actor The actor to add, cannot be null.
     */
    @Override
    public void add(final A actor)
    {
        if (actor == null) {
            throw new IllegalArgumentException("The given actor cannot be null.");
        }

        final int halfWidth = actor.getWidth()/2;
        final int minX = (int)Math.floor((actor.getX() - halfWidth) / (float)gridWidth);
        final int maxX = (int)Math.ceil( (actor.getX() + halfWidth) / (float)gridWidth);

        final int halfHeight = actor.getHeight()/2;
        final int minY = (int)Math.floor((actor.getY() - halfHeight) / (float)gridHeight);
        final int maxY = (int)Math.ceil( (actor.getY() + halfHeight) / (float)gridHeight);
        final Class<? extends A> actorClass = (Class<? extends A>) actor.getClass();
        
        // add actor to the grid
        for (int x = minX; x <= maxX; ++x) {
            for (int y = minY; y <= maxY; ++y) {
                Resizable2DArray<CachingHashSet<A>> classGrid = grid.get((Class<? extends A>) actorClass);
                CachingHashSet<A> actors;
                if (classGrid == null) {
                    classGrid = new Resizable2DArray<CachingHashSet<A>>();
                    actors = new CachingHashSet<A>();

                    classGrid.set( x, y, actors );
                    grid.put((Class<? extends A>) actorClass, classGrid);
                } else {
                    actors = classGrid.get( x, y );
                    if (actors == null) {
                        actors = new CachingHashSet<A>();
                        classGrid.set( x, y, actors );
                    }
                }

                actors.add( actor );
            }
        }

        actorGridPoints.put( actor, newRectangle(minX, maxX, minY, maxY) );
    }
    
    /**
     * Removes the given Actor from all parts of the collision grid.
     * @param actor The Actor to remove from the Grid.
     */
    @Override
    public void remove(final A actor)
    {
        lazyUpdateActors.remove( actor );
        final int[] points = actorGridPoints.remove( actor );
        ARRAYS.push( points );

        final Resizable2DArray<CachingHashSet<A>> actorGrid = grid.get((Class<? extends A>) actor.getClass());
        // you should presume that if the Actor has actorGridPoints then it is
        // also in the actorGrid, so no checks are needed

        final int minX = points[0];
        final int maxX = points[1];
        final int minY = points[2];
        final int maxY = points[3];
        
//        final int halfWidth = actor.getWidth()/2;
//        final int minX = (int)Math.floor((actor.getX() - halfWidth) / (float)gridWidth);
//        final int maxX = (int)Math.ceil( (actor.getX() + halfWidth) / (float)gridWidth);
//
//        final int halfHeight = actor.getHeight()/2;
//        final int minY = (int)Math.floor((actor.getY() - halfHeight) / (float)gridHeight);
//        final int maxY = (int)Math.ceil( (actor.getY() + halfHeight) / (float)gridHeight);

        for (int x = minX; x <= maxX; x++) {
            for (int y = minY; y <= maxY; y++) {
                actorGrid.get( x, y ).remove( actor );
            }
        }
    }
    
    /**
     * Updates the given actors details in the grid collissions. It should
     * already have been added to this CollisionHandler.
     * @param actor The actor to update.
     */
    /* It actually just stores that the actor should be update sometime in the
     * future. This is because often Actors need to be updated multiple times
     * before they are involved in a collision check. */
    @Override
    public void update(final A actor)
    {
        lazyUpdateActors.add( actor );
    }
    
    /**
     * Updates all the stored Actors collision information about which grid
     * cells they reside within.
     * The idea is that this is called at the latest possible moment to ensure
     * that Actors collision information is updated on demand.
     */
    private void lazyUpdate()
    {
        lazyUpdateActors.iterate( updateCallback );
        lazyUpdateActors.clear();
    }

    /**
     * Finds all objects that is an instance of at least one of the given
     * collisionClasses and intersects the given actor.
     * If no classes are provided then an empty set is returned.
     * @param actor The actor to check intersections against, cannot be null.
     * @param collisionClasses The types of actors to search for, cannot be null.
     * @return A set containing all of the actors that the given actor intersected with.
     */
    @Override
    public Set<A> getIntersectingActors(final A actor, final Class<? extends A> ... collisionClasses)
    {
        if (actor == null) {
            throw new IllegalArgumentException("The given actor cannot be null.");
        }
        
        applyToIntersectingActors(
                actor, getIntersectingActorsAction.initialize(), collisionClasses );
        return getIntersectingActorsAction.intersections;
    }
    
    /**
     * Essentially the same as getIntersectingActors, only this returns the
     * first actor found. If there are multiple actors that intersect the given
     * actor, then it should be presumed that one at random is returned.
     * @param actor The actor to find intersections against.
     * @param collisionClasses The type of actors to be checking for.
     * @return The first actor found that intersects the given actor.
     */
    @Override
    public A getIntersectingActor(final A actor, final Class<? extends A> ... collisionClasses)
    {
        if (actor == null) {
            throw new IllegalArgumentException("The given actor cannot be null.");
        }

        lazyUpdate();
        
        final int halfWidth = actor.getWidth()/2;
        final int minX = (int)Math.floor((actor.getX() - halfWidth) / (float)gridWidth);
        final int maxX = (int)Math.ceil( (actor.getX() + halfWidth) / (float)gridWidth);

        final int halfHeight = actor.getHeight()/2;
        final int minY = (int)Math.floor((actor.getY() - halfHeight) / (float)gridHeight);
        final int maxY = (int)Math.ceil( (actor.getY() + halfHeight) / (float)gridHeight);

        final int collisionClassesSize = collisionClasses.length;
        
        for (int i = 0; i < collisionClassesSize; ++i) {
            final Class<? extends A> collisionClass = collisionClasses[i];
            final ArrayList<Resizable2DArray<CachingHashSet<A>>> classPointsList = grid.getSubKeys( collisionClass );
            final int classPointsListSize = classPointsList.size();

            for (int j = 0; j < classPointsListSize; ++j) {
                final Resizable2DArray<CachingHashSet<A>> classPoints = classPointsList.get(j);
                
                if (classPoints != null) {
                    for (int x = minX; x <= maxX; x++) {
                        for (int y = minY; y <= maxY; y++) {
                            final CachingHashSet<A> otherActorPoints = classPoints.get( x, y );

                            if (otherActorPoints != null) {
                                for (final A otherActor : otherActorPoints) {
                                    // the actor v actor specific check
                                    if (actor != otherActor && actor.intersects(otherActor)) {
                                        return otherActor;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        
        return null;
    }

    /**
     * The same as getIntersectingActors only instead returning a set of the
     * actors that intersect the given actor, you pass in an object to apply to
     * them. This is more efficient because it avoids creating a set, and you
     * iterate over less actors.
     * @param actor The actor to test for an intersection against, cannot be null.
     * @param action The action to apply to all actors that intersect the given actor, cannot be null.
     * @param collisionClasses The types of actors to be testing for, cannot be null.
     * @return True if the action was applied to at least 1 actor, false if not.
     */
    public boolean applyToIntersectingActors(A actor, Action<A> action, Class<? extends A>... collisionClasses)
    {
        if (actor == null) {
            throw new IllegalArgumentException("The given actor cannot be null.");
        } else if (action == null) {
            throw new IllegalArgumentException("The given action cannot be null.");
        }

        lazyUpdate();

        final int collisionClassesSize = collisionClasses.length;
        // this must be initialized once, to avoid doing it multiple times
        gridCallback.initialize(actor, action);

        for (int i = 0; i < collisionClassesSize; ++i) {
            final Class<? extends A> collisionClass = collisionClasses[i];
            grid.iterateSubKeys( collisionClass, gridCallback );
        }

        return collisionCallback.popIsIntersection();
    }

    /**
     * The same as applyToIntersectingActors only this will apply the action to
     * the first Actor found, that is an instance of one of the given classes
     * and intersects the given actor.
     * @param actor The actor to find intersections against, cannot be null.
     * @param action The action to perform on the first actor found.
     * @param collisionClasses The types of actor to be finding.
     * @return True if the action was applied to an actor, false if not.
     */
    public boolean applyToIntersectingActor(A actor, Action<A> action, Class<? extends A>... collisionClasses)
    {
        if (actor == null) {
            throw new IllegalArgumentException("The given actor cannot be null.");
        } else if (action == null) {
            throw new IllegalArgumentException("The given action cannot be null.");
        }
        
        lazyUpdate();

        final int halfWidth = actor.getWidth()/2;
        final int minX = (int)Math.floor((actor.getX() - halfWidth) / (float)gridWidth);
        final int maxX = (int)Math.ceil( (actor.getX() + halfWidth) / (float)gridWidth);

        final int halfHeight = actor.getHeight()/2;
        final int minY = (int)Math.floor((actor.getY() - halfHeight) / (float)gridHeight);
        final int maxY = (int)Math.ceil( (actor.getY() + halfHeight) / (float)gridHeight);

        final int collisionClassesSize = collisionClasses.length;

        for (int i = 0; i < collisionClassesSize; ++i) {
            final Class<? extends A> collisionClass = collisionClasses[i];
            final ArrayList<Resizable2DArray<CachingHashSet<A>>> classPointsList = grid.getSubKeys( collisionClass );
            final int classPointsListSize = classPointsList.size();

            for (int j = 0; j < classPointsListSize; ++j) {
                final Resizable2DArray<CachingHashSet<A>> classPoints = classPointsList.get(j);

                if (classPoints != null) {
                    for (int x = minX; x <= maxX; ++x) {
                        for (int y = minY; y <= maxY; ++y) {
                            final CachingHashSet<A> otherActorPoints = classPoints.get( x, y );

                            if (otherActorPoints != null) {
                                for (final A otherActor : otherActorPoints) {
                                    // the actor v actor specific check
                                    if (actor != otherActor && actor.intersects(otherActor)) {
                                        action.action( otherActor );
                                        return true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        
        return false;
    }

    private final class CollisionCallback implements CallbackIterator<A>
    {
        private A actor;
        private Action<A> action;
        private boolean isIntersection;

        public CollisionCallback()
        {
            actor  = null;
            action = null;
            isIntersection = false;
        }

        public final CollisionCallback initialize(final A actor, final Action<A> action)
        {
            this.actor  = actor;
            this.action = action;
            return this;
        }

        public final void iterate(A otherActor)
        {
            if (actor != otherActor && actor.intersects(otherActor)) {
                action.action( otherActor );
                isIntersection = true;
            }
        }

        public boolean popIsIntersection()
        {
            final boolean temp = isIntersection;
            isIntersection = false;
            return temp;
        }
    }

    private final class UpdateCallback implements CallbackIterator<A>
    {
        public final void iterate(A actor)
        {
            final int[] points = actorGridPoints.get( actor );
            
            final int halfWidth = actor.getWidth()/2;
            final int minX = (int)Math.floor((actor.getX() - halfWidth) / (float)gridWidth);
            final int maxX = (int)Math.ceil( (actor.getX() + halfWidth) / (float)gridWidth);

            final int halfHeight = actor.getHeight()/2;
            final int minY = (int)Math.floor((actor.getY() - halfHeight) / (float)gridHeight);
            final int maxY = (int)Math.ceil( (actor.getY() + halfHeight) / (float)gridHeight);

            // if we got a new array of points back
            final Resizable2DArray<CachingHashSet<A>> classGrid = grid.get((Class<? extends A>) actor.getClass());

            final int oldMinX = points[0];
            final int oldMaxX = points[1];
            final int oldMinY = points[2];
            final int oldMaxY = points[3];

            final int totalMinX = Math.min( minX, oldMinX );
            final int totalMaxX = Math.max( maxX, oldMaxX );
            final int totalMinY = Math.min( minY, oldMinY );
            final int totalMaxY = Math.max( maxY, oldMaxY );

            for (int x = totalMinX; x <= totalMaxX; ++x) {
                for (int y = totalMinY; y <= totalMaxY; ++y) {
                    // if we are in the new rectangle
                    if (minX <= x && x <= maxX && minY <= y && y <= maxY) {
                        // if we are outside the old rectangle, add
                        if ( !(oldMinX <= x && x <= oldMaxX && oldMinY <= y && y <= oldMaxY) ) {
                            CachingHashSet<A> actors = classGrid.get(x, y);

                            if (actors == null) {
                                actors = new CachingHashSet<A>();
                                classGrid.set( x, y, actors );
                            }

                            actors.add( actor );
                        }
                    // if we are no int the new rectangle and are in the old rectangle, remove
                    } else if ( oldMinX <= x && x <= oldMaxX && oldMinY <= y && y <= oldMaxY ) {
                        classGrid.get( x, y ).remove( actor );
                    }
                }
            }
            
            points[0] = minX;
            points[1] = maxX;
            points[2] = minY;
            points[3] = maxY;
        }
    }

    private final class GridCallback implements CallbackIterator<Resizable2DArray<CachingHashSet<A>>>
    {
        private int minX;
        private int maxX;
        private int minY;
        private int maxY;

        private A actor;
        private Action<A> action;

        public final void initialize(A actor, Action<A> action)
        {
            this.actor  = actor;
            this.action = action;

            final int halfWidth = actor.getWidth()/2;
            minX = (int)Math.floor((actor.getX() - halfWidth) / (float)gridWidth);
            maxX = (int)Math.ceil( (actor.getX() + halfWidth) / (float)gridWidth);

            final int halfHeight = actor.getHeight()/2;
            minY = (int)Math.floor((actor.getY() - halfHeight) / (float)gridHeight);
            maxY = (int)Math.ceil( (actor.getY() + halfHeight) / (float)gridHeight);
        }

        public void iterate(Resizable2DArray<CachingHashSet<A>> classPoints)
        {
            if (classPoints != null) {
                for (int x = minX; x <= maxX; ++x) {
                    for (int y = minY; y <= maxY; ++y) {
                        final CachingHashSet<A> otherActorPoints = classPoints.get( x, y );

                        if (otherActorPoints != null) {
                            otherActorPoints.iterate( collisionCallback.initialize(actor, action) );
                        }
                    }
                }
            }
        }
    }

    /**
     * This is the action used by getIntersectingActors in order for it to just
     * be piped into the applyToIntersectingActors method.
     */
    private final class IntersectingActorsAction implements Action<A>
    {
        private Set<A> intersections;
        
        public final IntersectingActorsAction initialize()
        {
            intersections = new HashSet<A>();
            return this;
        }

        public void action(A actor)
        {
            intersections.add( actor );
        }
    };
}
